package 中等.动态规划.其他;

import java.util.*;

/**
 * 给你一个整数 n 表示数轴上的房屋数量，编号从 0 到 n - 1 。
 * 另给你一个二维整数数组 offers ，其中 offers[i] = [starti, endi, goldi]
 * 表示第 i 个买家想要以 goldi 枚金币的价格购买从 starti 到 endi 的所有房屋。
 * 作为一名销售，你需要有策略地选择并销售房屋使自己的收入最大化。
 * 返回你可以赚取的金币的最大数目。
 * 注意 同一所房屋不能卖给不同的买家，并且允许保留一些房屋不进行出售。
 */
public class 销售利润最大化_2830 {

    public static void main(String[] args) {

        System.out.println(maximizeTheProfit(5, Arrays.asList(
                Arrays.asList(0, 0, 1),
                Arrays.asList(0, 2, 2),
                Arrays.asList(1, 3, 2)
        )));

    }

    /**
     * 动态规划
     * 1，子问题
     * dp [i] 表示 [0,i] 可以获取的最大利润是多少
     * 2，状态转移方程
     * a. 卖 或者 不卖
     * 某个 [start,end] 收购 gold，end = i
     * dp[i] = Math.max(dp[i-1],dp[start-1] + gold)
     * b. 枚举所有以 i 结尾的方案，取最大值
     */
    public static int maximizeTheProfit(int n, List<List<Integer>> offers) {
        Map<Integer, List<List<Integer>>> map = new HashMap<>();
        offers.forEach(offer -> {
            List<List<Integer>> lists = map.get(offer.get(1));
            if (lists == null) {
                lists = new ArrayList<>();
                map.put(offer.get(1), lists);
            }
            lists.add(offer);
        });

        // 防止 start-1 < 0 ，dp[i] 表示 [0,i-1] 的房屋
        int[] dp = new int[n + 1];
        for (int i = 0; i < n; i++) {
            List<List<Integer>> lists = map.get(i);
            if (lists == null) {
                dp[i + 1] = dp[i];
                continue;
            }
            for (List<Integer> list : lists) {
                int start = list.get(0), gold = list.get(2);
                int curProfit = Math.max(dp[i], dp[start] + gold);

                dp[i + 1] = Math.max(dp[i + 1], curProfit);
            }
        }

        return dp[n];
    }

}
